package me.algo.tree;

import java.util.LinkedList;
import java.util.Objects;

/**
 * @author guozheng
 * @date 2024/5/4
 */
public class T15 {
    /**
     * 1609. 奇偶树
     * @param root
     * @return
     */
    public static boolean isEvenOddTree(TreeNode root) {
        if (Objects.isNull(root)) {
            return false;
        }
        LinkedList<Pair> que = new LinkedList<>();
        que.addLast(new Pair(0, root));
        while (!que.isEmpty()) {
            int size = que.size();
            if (size <= 0) {
                continue;
            }
            Pair pair = que.peekFirst();
            int level = pair.level;
            int nextLevel = level + 1;
            int last = 0;
            int total = size;
            while (total > 0) {
                Pair p = que.removeFirst();
                TreeNode nd = p.node;
                if (total == size) {
                    if (!valid(level, nd.val)) {
                        return false;
                    }
                    last = nd.val;
                } else {
                    boolean b = validEq(level, last, nd.val);
                    if (!b) {
                        return false;
                    }
                    last = nd.val;
                }
                if (nd.left != null) {
                    que.addLast(new Pair(nextLevel, nd.left));
                }
                if (nd.right != null) {
                    que.addLast(new Pair(nextLevel, nd.right));
                }
                total--;
            }
        }
        return true;
    }

    static boolean valid(int level, int val) {
        if (level % 2 == 0) {
            if (val % 2 == 0) {
                return false;
            }
        } else {
            if (val % 2 == 1) {
                return false;
            }
        }
        return true;
    }
    static boolean validEq(int level, int last, int current) {
        if (level % 2 == 0) {
            // 0/2/4/6层 奇数 自增
            if (current % 2 == 0) {
                // 偶数为false
                return false;
            }
            if (current <= last) {
                // 不大于上一个false
                return false;
            }
        } else {
            // 1/3/5/7层  偶数  递减
            if (current % 2 == 1) {
                return false;
            }
            if (current >= last) {
                return false;
            }
        }
        return true;
    }

    record Pair(int level, TreeNode node) {

    }



}
